#define _CRT_SECURE_NO_WARNINGS 1
#include <stdbool.h>
#include <stdio.h>

 // 622. 设计循环队列


// 用数组实现
typedef struct
{
    int* a;
    int front;
    int tail;
    int k;
} MyCircularQueue;

bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueIsEmpty(MyCircularQueue* obj);

MyCircularQueue* myCircularQueueCreate(int k)
{
    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    cq->a = (int*)malloc(sizeof(int) * (k + 1));
    cq->front = cq->tail = 0;
    cq->k = k;
    return cq;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->a[obj->tail] = value;
    obj->tail++;
    obj->tail %= (obj->k + 1);
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
        return false;
    if (obj->front == obj->k)
    {
        obj->front = 0;
    }
    else
    {
        obj->front++;
    }
    return  true;

}

int myCircularQueueFront(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
        return -1;
    return obj->a[obj->front];

}

int myCircularQueueRear(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
        return -1;
    if (obj->tail == 0)
    {
        return obj->a[obj->k];
    }
    return obj->a[obj->tail - 1];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
    return obj->tail == obj->front;
}

bool myCircularQueueIsFull(MyCircularQueue* obj)
{
    return (obj->tail + 1) % (obj->k + 1) == obj->front;
}

void myCircularQueueFree(MyCircularQueue* obj)
{
    free(obj->a);
    free(obj);
}

    // 用链表实现
  

typedef struct QueueNode
{
    int data;
    struct QueueNode* next;
}QueueNode;

typedef struct
{
    QueueNode* head;
    QueueNode* tail;
    int k;
} MyCircularQueue;

//函数声明
bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueIsEmpty(MyCircularQueue* obj);

MyCircularQueue* myCircularQueueCreate(int k)
{
    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    cq->k = k;
    cq->head = cq->tail = NULL;
    // 创建k+1个节点的循环链表
    int temp = k + 1;
    while (temp--)
    {
        QueueNode* NewNode = (QueueNode*)malloc(sizeof(QueueNode));
        NewNode->next = NULL;
        if (cq->head == NULL)
        {
            cq->head = cq->tail = NewNode;
        }
        else
        {
            cq->tail->next = NewNode;
            cq->tail = NewNode;
        }
    }
    cq->tail->next = cq->head;
    cq->tail = cq->head;
    return cq;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }

    obj->tail->data = value;
    obj->tail = obj->tail->next;

    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
    {
        return false;
    }

    obj->head = obj->head->next;

    return true;
}

int myCircularQueueFront(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }

    return obj->head->data;
}

int myCircularQueueRear(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    QueueNode* current = obj->head;
    while (current->next != obj->tail)
    {
        current = current->next;
    }
    return current->data;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
    if (obj->head == obj->tail)
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool myCircularQueueIsFull(MyCircularQueue* obj)
{
    if (obj->tail->next == obj->head)
    {
        return true;
    }
    else
    {
        return false;
    }
}

void myCircularQueueFree(MyCircularQueue* obj)
{
    QueueNode* current = obj->head->next;
    while (current != obj->head)
    {
        QueueNode* next = current->next;
        free(current);
        current = next;
    }
    free(obj->head);
    free(obj);
}




  //232. 用栈实现队列

typedef int STDataType;
typedef struct Stack
{
    STDataType* a;
    int top; // 栈顶
    int capacity; // 容量
}Stack;

typedef struct
{
    Stack st1; // 专门用来进
    Stack st2;//专门用来出
} MyQueue;

void StackInit(Stack* ps)
{
    assert(ps);
    STDataType* temp = (STDataType*)malloc(sizeof(STDataType) * 4);
    if (temp == NULL)
    {
        perror("malloc");
        exit(-1);
    }
    ps->a = temp;
    ps->top = 0;
    ps->capacity = 4;
}
void StackCheckCapacity(Stack* ps)
{
    assert(ps);
    // 扩容
    if (ps->top == ps->capacity)
    {
        STDataType* temp = (STDataType*)realloc(ps->a, sizeof(STDataType) * 2 * ps->capacity);
        if (temp == NULL)
        {
            perror("realloc");
            exit(-1);
        }
        ps->a = temp;
        ps->capacity = 2 * ps->capacity;
    }
}

bool StackEmpty(Stack* ps)
{
    assert(ps);
    // 空时返回true，不为空返回false
    return ps->top == 0;
}


void StackPush(Stack* ps, STDataType data)
{
    assert(ps);
    StackCheckCapacity(ps);
    ps->a[ps->top] = data;
    ps->top++;
}

STDataType StackTop(Stack* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->a[ps->top - 1];
}


void StackDestroy(Stack* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

void StackPop(Stack* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    ps->top--;
}

int StackSize(Stack* ps)
{
    assert(ps);
    return ps->top;
}






MyQueue* myQueueCreate()
{
    MyQueue* Queue = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&Queue->st1);
    StackInit(&Queue->st2);
    return Queue;
}

void myQueuePush(MyQueue* obj, int x)
{
    StackPush(&obj->st1, x);
}

int myQueuePop(MyQueue* obj)
{
    if (StackEmpty(&obj->st2) == true)
    {
        int temp = StackSize(&obj->st1);
        while (temp--)
        {
            StackPush(&obj->st2, StackTop(&obj->st1));
            StackPop(&obj->st1);
        }
    }

    int ret = StackTop(&obj->st2);
    StackPop(&obj->st2);
    return ret;
}


int myQueuePeek(MyQueue* obj)
{
    if (StackEmpty(&obj->st2) == true)
    {
        int temp = StackSize(&obj->st1);
        while (temp--)
        {
            StackPush(&obj->st2, StackTop(&obj->st1));
            StackPop(&obj->st1);
        }
    }
    int ret = StackTop(&obj->st2);

    return ret;
}

bool myQueueEmpty(MyQueue* obj)
{
    return StackEmpty(&obj->st1) && StackEmpty(&obj->st2);
}

void myQueueFree(MyQueue* obj)
{
    StackDestroy(&obj->st1);
    StackDestroy(&obj->st2);
    free(obj);
}

    // 225. 用队列实现栈
typedef int QDataType;
//链式结构：表示队列
typedef struct QListNode
{
    struct QListNode* next;
    QDataType data;
}QNode;

// 队列的结构
typedef struct Queue
{
    QNode* head;
    QNode* tail; // 便于尾插
}Queue;


typedef struct
{
    Queue q1;
    Queue q2;
} MyStack;

void QueueInit(Queue* q)
{
    assert(q);
    q->head = NULL;
    q->tail = NULL;
}

void QueuePush(Queue* q, QDataType data)
{
    assert(q);
    QNode* newNode = (QNode*)malloc(sizeof(QNode));
    newNode->data = data;
    newNode->next = NULL;
    // 第一次插入
    if (q->head == NULL)
    {
        q->head = q->tail = newNode;
    }
    else
    {
        q->tail->next = newNode;
        q->tail = newNode;
    }
}

bool QueueEmpty(Queue* q)
{
    assert(q);
    return q->head == NULL;
}


void QueuePop(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    QNode* next = q->head->next;
    free(q->head);
    q->head = next;
    if (q->head == NULL)
    {
        q->tail = NULL;
    }

}


QDataType QueueFront(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->head->data;
}

QDataType QueueBack(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->tail->data;
}


int QueueSize(Queue* q)
{
    assert(q);
    int count = 0;
    QNode* current = q->head;
    while (current != NULL)
    {
        count++;
        current = current->next;
    }
    return count;
}

void QueueDestroy(Queue* q)
{
    assert(q);
    QNode* current = q->head;
    while (current != NULL)
    {
        QNode* next = current->next;
        free(current);
        current = next;
    }
    q->head = q->tail = NULL;
}





MyStack* myStackCreate()
{
    MyStack* Stack = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&Stack->q1);
    QueueInit(&Stack->q2);
    return Stack;
}

void myStackPush(MyStack* obj, int x)
{
    Queue* Empty = &obj->q1;
    Queue* nonEmpty = &obj->q2;
    if (!QueueEmpty(&obj->q1))
    {
        Empty = &obj->q2;
        nonEmpty = &obj->q1;
    }
    QueuePush(nonEmpty, x);

}

int myStackPop(MyStack* obj)
{
    Queue* Empty = &obj->q1;
    Queue* nonEmpty = &obj->q2;
    if (!QueueEmpty(&obj->q1))
    {
        Empty = &obj->q2;
        nonEmpty = &obj->q1;
    }
    while (QueueSize(nonEmpty) > 1)
    {
        QueuePush(Empty, QueueFront(nonEmpty));
        QueuePop(nonEmpty);
    }
    int ret = QueueFront(nonEmpty);
    QueuePop(nonEmpty);
    return ret;
}

int myStackTop(MyStack* obj)
{
    Queue* Empty = &obj->q1;
    Queue* nonEmpty = &obj->q2;
    if (!QueueEmpty(&obj->q1))
    {
        Empty = &obj->q2;
        nonEmpty = &obj->q1;
    }
    return QueueBack(nonEmpty);
}

bool myStackEmpty(MyStack* obj)
{
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj)
{
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}


